package algorithm.heap;

import org.omg.CORBA.CODESET_INCOMPATIBLE;

/**
 * @author bingo
 * @Description 最小堆
 * @Date 2018/4/17
 */
public class MinHeap {


    public Integer[] data;

    public Integer count;

    public Integer size;

    public MinHeap(Integer size) {
        this.data = new Integer[size+1];
        this.count = 0;
        this.size = size;
    }

    public MinHeap() {


    }

    public  void insert(int i){

        data[count+1] = i;
        count++;
        shiftUp(count);

    }

    private void shiftUp(int k) {

        while (k > 1 && data[k] < data[k/2]){
            int temp = data[k/2];
            data[k/2] = data[k];
            data[k] = temp;
            k=k/2;

        }

    }

    public  Integer pop(){

        int number = data[1];
        int temp = data[1];
        data[1] = data[count];
        data[count] = temp;
        count--;
        shiftDown(1);

        return  number;
    }

    private void shiftDown(int k) {

        while (2*k <= count){
            int j=2*k;
            if(j+1<=count&&data[j+1]<data[j]){
                j++;
            }

            if(data[k]<=data[j]){
                break;
            }
            int temp = data[k];
            data[k] = data[j];
            data[j] = temp;
            k=j;
        }
    }

    public  Integer size(){

        return size;
    }

    public static void main(String[] args) {
        MinHeap minHeap = new MinHeap(50);
        for(int i=0;i<50;i++){
            minHeap.insert(i);
        }

        for(int i=0;i<50;i++){
            int n= minHeap.pop();
            System.out.print(n+",");

        }
    }
}
